1. Field of the Invention
The present invention relates to techniques for improving the performance of computer systems. More specifically, the present invention relates to a method and an apparatus for duplicating cache lines in response to a way prediction conflict in a cache memory.
2. Related Art
Some computer systems include data and/or instruction caches that are “set-associative.” Generally, in a set-associative cache, the entries in the cache are logically divided into a number of “sets” and “ways.” A “set” is a group of cache entries that are used to store cache lines from the same predetermined range of physical addresses, while a “way” is a logical division of the entries in the cache into two or more similar groups. A set has exactly one entry in each way (e.g., see the set shown by hash marks in way 102 and way 104 in FIG. 1).
Some multi-way caches use “way prediction” to improve performance when accessing cache lines. In such caches, upon accessing (i.e., reading or writing) a cache line in a given way, a cache controller records the way in which the cache line was accessed. When subsequently accessing the cache line, the cache controller uses the recorded way to predict the way in which the cache line resides. Way prediction can speed up cache line accesses by taking advantage of the fact that cache lines are often found in the same way in which the cache line was most recently accessed.
In some caches, the ways are recorded in a “way prediction table.” Some of these caches use a function (e.g., a “hash function” or another function) to identify an entry within the way prediction table when recording the way in which the cache line was accessed or when subsequently retrieving the recorded way.
FIG. 1 presents block diagram illustrating a cache 100 that uses way prediction. Cache 100 includes way 102, way 104, cache controller 106, and way prediction table 108. During operation, upon receiving a cache line to be accessed, cache controller 106 computes an entry in way prediction table 108 using the cache line's address as an input into the hash function for way prediction table 108. If there is a way recorded in the entry, cache controller 106 uses the recorded way as a prediction of the way where the cache line resides. Cache controller 106 then checks for the cache line in only the predicted way. Otherwise, if there is no entry in way prediction table 108, cache controller 106 checks both ways for the cache line.
If the cache line is present in the predicted way, cache controller 106 accesses the cache line in that way. Otherwise, cache controller 106 checks the remaining way for the cache line. If the cache line is present in the other way, the way was mispredicted and cache controller 106 accesses the cache line in that way. If the way was mispredicted (or if there was no way recorded in the entry), cache controller 106 records the correct way in way prediction table 108. The entries in way prediction table 108 are updated in this fashion for each misprediction.
Because the entries in way prediction table 108 are updated for each misprediction, some patterns of cache line accesses can negate the benefit of way prediction. One such pattern occurs when two or more cache lines are being accessed in different ways wherein the hash function for way prediction table 108 returns in the same entry in the way prediction table 108 for both cache lines. For example, assume that cache lines A and B are being accessed in an A-B-A-B . . . pattern; cache line A in way 102 and cache line B in way 104 (as shown in FIG. 1). Assume further that the hash function for way prediction table 108 returns entry E for both the address for cache line A and the address for cache line B. As described above, accessing cache line A causes cache controller to update entry E in way prediction table 108 to indicate way 102, while accessing cache line B causes cache controller to update entry E in way prediction table 108 to indicate way 104. Thus, when cache lines A and B are accessed in alternating pattern, the way is always mispredicted by cache controller 106. Because of the way misprediction, cache controller 106 incurs additional delay and consumes additional power while first checking in the predicted way and then checking in the other way for each cache line.